279. 完全平方数

Similar Question

Solution Tips

方案一: 完全背包

var numSquares = function(n) {
    // 也是完全背包的题目
    // target 即是 n
    // 可选的物品即是完全平方数的集合, 然后是有一个上界的 也是 n 自身
    // 12 只可能由 1 2 4 9 组成
    const dp = Array.from({ length: n + 1 }, () => 100000);
    dp[0] = 0;
    for (let i = 1; i * i <= n ; i++) {
        // amount
        for (let j = i * i; j <= n; j++) {
            const item = i * i;
            // 不选择 item 和 选择了 item
            dp[j] = Math.min(dp[j], dp[j - item] + 1);
        }
    }

    return dp[n];
};